package com.algorithm.learning.base.图;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/27 22:50
 **/
public class 并查集 {

    public static class Node<V> {
        private V v;

        public Node(V v) {
            this.v = v;
        }
    }

    /**
     * 并查集
     *
     * 1、有若干元素 a、b、c、d、e、f等，它们的类型都是V
     * 2、在并查集中初始情况 每个元素的都在单独的集合中
     * 3、用户可以在任何时候调用两个方法：
     *    boolean isSameSet(V a, V b): 查询元素a和元素b是否属于一个集合
     *    void union(V a, V b): 将元素a和元素b所在的所有集合合并成一个集合
     * 其中isSameSet和union的代价越低越好
     *
     * 我们来解释下上面的意思：
     * 假如有a、b、c、d、e五个样本，它们一开始的集合就是它们自己本身的节点。
     * a ∈ {a}
     * b ∈ {b}
     * c ∈ {c}
     * d ∈ {d}
     * e ∈ {e}
     *
     * 那么此时，我调用isSameSet(a, b) 得到的结果肯定是false，因为a和b不在一个集合中。
     *
     * 但是我可以调用union(a, b), 将a和b所在的集合合并成一个集合,此时的结构就是:
     * a ∈ {a, b}, b ∈ {a, b}
     * 这里我们可以用代码来理解，比如元素a对于一个节点就是Node_A, 元素b对应的节点就是Node_B,
     *
     * 首先在初识状态下，每一个节点都是自己的集合，其次合并的规则为，比较两个集合的大小：
     * 1、如果大小相等，那就随便选一个集合合并到另一个集合
     * 2、如果大小不相等，那么就让小集合合并到大集合中
     *
     *
     * a -> Node_A
     * b -> Node_B
     *
     * 那么如果把元素a和元素b对应的集合合并，那么就相当于，把Node_B的头节点指向Node_A
     * Node_A -> Node_A
     * Node_B -> Node_A
     *
     * 如果我想把元素c的集合，与元素a集合进行合并，那么我们把小集合 合并到 大集合中：
     * 元素c的集合只有一个那就是Node_C, 而元素a的集合有两个，Node_A、Node_B
     * 所以把元素c的集合，合并到元素a的集合中，合并的方式，就是把Node_C 指向，Node_A的父节点顶部节点（可以理解为根节点），依然是Node_A
     * 那么此时的结构为:
     * Node_A -> Node_A
     * Node_B -> Node_A
     * Node_C -> Node_A
     *
     * 那么此时，元素a,b,c都属于同一集合, 因为这三个元素都一个公共的父节点，那就是Node_A
     *
     * 如果我想把元素d的集合，与元素e集合进行合并，这两个集合大小一样，所以随便合并：
     * Node_D -> Node_D
     * Node_E -> Node_D
     *
     *  那么此时，元素d, e都属于同一集合, 因为这两个元素都一个公共的父节点，那就是Node_D
     *
     * 如果我们想到元素e的集合，与元素c集合进行合并，那么元素e集合只有两个元素，而元素c有三个元素，所以小集合合并到大集合：
     * 合并的规则，就是把元素e的根节点，指向元素c的根节点即可，那么最后的结构为：
     * Node_A -> Node_A
     * Node_B -> Node_A
     * Node_C -> Node_A
     *
     * Node_D -> Node_A
     * Node_E -> Node_D
     *
     * 那么此时，元素a、b、c、d、e都属于同一集合, 因为这五个元素都一个公共的父节点，那就是Node_A
     *
     * 那么根据上面的规则，实际上可以理解为，一个根节点就表示一个集合
     * @param <V>
     */
    public static class UnionSet<V> {
        // 元素与节点的映射，即 a -> Node_A
        private Map<V, Node<V>> nodes = new HashMap<>();
        // 元素与父节点的映射，即 Node_A -> Node_A, Node_B -> Node_A...
        private Map<Node<V>, Node<V>> parentsMap = new HashMap<>();
        // 根节点与集合大小映射，即 Node_A -> 5
        private Map<Node<V>, Integer> sizeMap = new HashMap<>();

        /**
         * 构造并查集
         * @param values
         */
        public UnionSet(List<V> values) {
            // 这里很好理解，就是初始化集合，每个元素都是单独的集合
            for (V value : values) {
                Node<V> node = new Node<>(value);
                nodes.put(value, node);
                parentsMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        /**
         * 这个方法的目的，就是给一个节点，找到这个节点的根节点
         *
         * 注意：此方法有优化！！！
         *
         * 根据上面对于并查集的解释我们知道，如果元素a、b、c、d、e五个元素合并成一个元素时，得到的结果为：
         *       a
         *       ↑
         *       a
         *     ↗   ↖
         *    b     d
         *   ↗       ↖
         *  c         e
         *
         *  此时，我想加一个元素f，并且将f与元素c合并，很明显，我需要从元素c不断往上层找，直到找到根节点a，然后将元素f指向a。
         *  同时，判断两个元素是否一个集合，也是如此。
         *
         *  那么问题来了，如果这个集合很大，就会导致，每一次集合合并，或者判断时，都需要遍历整个上层链表，直到根节点，这样效率会很低。时间复杂度是O(N)
         *
         *  所以，我们可以通过优化，在每一次调用findParent方法时进行扁平化处理，
         *  我们直接将这个路径上的所有节点，全部都指向根节点。这样我们在下一次查找时，就可以直接找到对应的根节点，时间复杂度为O(1)
         *
         *  也就是说，当我们把元素f与元素c合并的时候，因为元素c要向上找到根节点，我们直接把找到根节点的这个路径上的所有元素全部指向根节点即可。
         *  得到的结构如下：
         *       a
         *       ↑
         *  b →  a ← c
         *     ↗  ↖
         *    f    d
         *         ↖
         *          e
         * 此时如果再有元素与元素c合并，那么我们直接可以找到对应的根节点
         *
         * @param cur
         * @return
         */
        public Node<V> findParent(Node<V> cur) {
            // 这里可以不用栈，用其他的都可以，集合/队列等等
            Stack<Node<V>> stack = new Stack<>();
            // 下面的循环，就是再找根节点
            // 如果 cur == parentsMap.get(cur) 的话，就说明，此时cur就是根节点，因为parentsMap的value存放的就是上层节点
            while (cur != parentsMap.get(cur)) {
                stack.push(cur);
                cur = parentsMap.get(cur);
            }
            while (!stack.isEmpty()) {
                parentsMap.put(stack.pop(), cur);
            }
            return cur;
        }

        /**
         * 判断两个元素是否属于同一个集合
         *
         * @param a
         * @param b
         * @return
         */
        public boolean isSameSet(V a, V b) {
            if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
                return false;
            }
            // 这里很好理解
            // 我们根据传入的元素，找到对应的节点，然后根据节点再一层一层网上找，直到找到其根节点，最后，比较这两个根节点是不是同一个，如果是，则表示是同一个集合
            return findParent(nodes.get(a)) == findParent(nodes.get(b));
        }

        public void union(V a, V b) {
            if (!nodes.containsKey(a) || !nodes.containsKey(b)) {
                return;
            }
            Node<V> aHead = findParent(nodes.get(a));
            Node<V> bHead = findParent(nodes.get(b));

            // 这里也很好理解，如果两个节点的根节点是同一个，那就表示这两个属于同一集合，没必要合并了
            if (aHead == bHead) {
                return;
            } else {
                Integer aSize = sizeMap.get(aHead);
                Integer bSize = sizeMap.get(bHead);
                // 这里说明，a的集合比b的大，那么就把b的集合合并到a的集合中
                if (aSize >= bSize) {
                    // 将b元素的根节点，直接指向 a元素的根节点即可
                    parentsMap.put(bHead, aHead);
                    // 同时将 a元素所在的集合大小，加上b集合的大小，就是现在a元素集合的大小
                    sizeMap.put(aHead, aSize + bSize);
                    // 要注意，sizeMap只是存放根节点对应的集合大小，所以需要把b元素的根节点的大小移出。
                    sizeMap.remove(bHead);
                } else {
                    parentsMap.put(aHead, bHead);
                    sizeMap.put(bHead, aSize + bSize);
                    sizeMap.remove(aHead);
                }

            }
        }

        /**
         * 获取并查集的大小，其实也就表示不同集合的个数。
         *
         * @return
         */
        public int getSizeNumber() {
            return sizeMap.size();
        }
    }


}
